#ifndef NODELIST_H
#define NODELIST_H

#include <iostream>
#include <sstream>
#include <string>

namespace algo {

  template<typename T>
  class NodeList;

  template<typename T>
  class NodeListElement {
  protected:
    NodeListElement() : prev(0), next(0) {}
    T *prev, *next;

    void clear() {
      prev = next = 0;
    }

    std::string dotString() const {
      std::ostringstream res;
      if (next)
        res << (size_t)this << " -> " << (size_t)next << "\n";
      if (prev)
        res << (size_t)this << " -> " << (size_t)prev << "\n";
      return res.str();
    }

    friend class NodeList<T>;
  };

  /**
   * Double likned list, where the element is the data-type itself and is thus 
   * required to inherit NodeListElement that contains the fields required.
   *
   * NB: All operations in this list is O(1).
   */
  template<typename T>
  class NodeList {
  public:
    NodeList() : length(0), first(0), last(0) {}

    T *front() const { return first; }
    T *back() const { return last; }

    void clear() {
      length = 0; first = 0; last = 0;
    }

    /**
     * Push a new element to the front of the list.
     */
    T *push_front(T *element) {
      element->clear();
      length++;
      if (isEmpty()) {
        first = last = element;
        return element;
      } 
      element->next = first;
      first = first->prev = element;

      return element;
    }

    /**
     * Push a new element to the back of the list.
     */
    T *push_back(T *element) {
      element->clear();
      length++;
      if (isEmpty()) {
        first = last = element;
        return element;
      } 
      element->prev = last;
      last = last->next = element;

      return element;
    }

    /**
     * Push an entire list to the front of the list. This will break the other list!
     */
    NodeList<T> &push_back(const NodeList<T> &other) {
      length += other.length;

      if (other.isEmpty())
        return *this;

      if (isEmpty()) {
        first = other.first;
        last = other.last;
        return *this;
      } 
      other.first->prev = last;
      last->next = other.first;
      last = other.last;

      return *this;
    }

    /**
     * Remove an element from the list.
     */
    void remove(T *element) {
      if (element == first)
        first = element->next;

      if (element == last)
        last = element->prev;

      if (element->next)
        element->next->prev = element->prev;

      if (element->prev)
        element->prev->next = element->next;

      length--;
    }

    /**
     * Create a string that is the dot-representation of this list. Purely for debuging,
     * but is, combined with DotProcessor, a very powerfull tool.
     */
    std::string dotString() {
      std::ostringstream res;
      res << "digraph NodeList {\nrankdir=LR \n";
      T *element = first;
      while(element) {
        res << element->dotString();
        element = element->next;
      }
      if (first)
        res << (size_t)this << " -> " << (size_t)first << "\n";
      if (last)
        res << (size_t)this << " -> " << (size_t)last << "\n";
      res << (size_t)this << " [label=\"List\"]\n";
      res << "}\n";
      return res.str();
    }

    /**
     * Get the size of the list.
     */
    size_t size() const { return length; }

    /**
     * Return true if the list is empty. Equivalent to calling 'size() == 0'.
     */
    bool isEmpty() const { return first == 0; }

  private:
    size_t length;
    T *first, *last;
  };
}

#endif //NODELIST_H
